package ex.algorithms.divideconquer;

public class MaximumSubarray {
	public static int[] findMaxSubarray(int[] input) {
		if(input == null)
			return null;
				
		return findMaxSubarray(input, 0, input.length -1);
	}
	
	public static int[] findMaxSubarray(int[] input, int low, int high) {
		if(low == high)
			return new int[] {low, high, input[low]};
		
		int mid = (high + low) / 2;
		
		int[] left = findMaxSubarray(input, low, mid);
		int[] right = findMaxSubarray(input, mid+1, high);
		int[] cross = findMaxCrossingSubarray(input, low, mid, high);
		
		if(left[2] >= right[2] && left[2] >= cross[2])
			return left;
		else if(right[2] >= left[2] && right[2] >= cross[2])
			return right;
		else
			return cross;
	}
	
	private static int[] findMaxCrossingSubarray(int[] input, int low, int mid, int high) {
		int leftMax = Integer.MIN_VALUE;
		int leftSum = 0;
		int leftBound = -1;
		for(int i=mid; i>=low; i--) {
			leftSum += input[i];
			if(leftSum >= leftMax) {
				leftMax = leftSum;
				leftBound = i;
			}
		}
		
		int rightMax = Integer.MIN_VALUE;
		int rightSum = 0;
		int rightBound = -1;
		for(int i=mid+1; i<=high; i++) {
			rightSum += input[i];
			if(rightSum >= rightMax) {
				rightMax = rightSum;
				rightBound = i;
			}
		}
		
		return new int[] {leftBound, rightBound, leftMax + rightMax};
	}
}
